/*
 * @Author: szx
 * @Date: 2022-03-12 13:49:33
 * @LastEditTime: 2022-03-12 13:57:32
 * @Description:
 * @FilePath: \leetcode\1-99\93\93_2.js
 */
var restoreIpAddresses = function (s) {
    const res = [];
    const len = s.length;
    const backtrack = (path, index) => {
        if (path.length > 4) return;
        if (index >= len && path.length == 4) {
            res.push(path.join('.'));
            return;
        }

        for (let i = index; i < len; i++) {
            if (i - index >= 3 || !isLegal(s, index, i)) continue;
            path.push(s.substring(index, i + 1));
            backtrack(path, i + 1);
            path.pop();
        }
    };
    const isLegal = (s, l, r) => {
        if (r - l > 0 && s[l] == '0') {
            return false;
        }
        for (let i = l; i <= r; i++) {
            if (!(s[i] >= '0' && s[i] <= '9')) {
                return false;
            }
        }
        const num = parseInt(s.substring(l, r + 1));
        if (num > 255 || num < 0) {
            return false;
        }
        return true;
    };
    backtrack([], 0);
    return res;
};



